#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 454
/**
	时间复杂度: O(n^2)
	空间复杂度: O(n^2)
*/
class FourSum{
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
		 // 键 c+d 加和的可能性; 值 可能性出现频率
		 unordered_map<int, int> map;	   
		 for(int i = 0;i < C.size();i++){
			for(int j = 0; j < D.size(); j++){
				map[C[i] + D[j]] += 1;
			}
		 }		
		 
		// A[i]+B[j] 所有可能性
		 int res = 0;
		 for(int i = 0; i < A.size();i++){
			for(int j = 0; j < B.size(); j++){
				if(map.find(-A[i]-B[j]) != map.end()){	// 在cd查找表中查找到 a+b 的绝对值
					res += map[-A[i]-B[j]];             // 记录 0-A[i]-B[j] 出现次数
				}
			}
		 }	
		 return res;
    }
}
